#include "MinimumDegreeSort.h"

#include <algorithm>
#include <vector>
#include <iostream>
#include "metis.h"

#include "Utility/Algebra/Matrix.h"
#include "DBManager/IService/Input/Element/IElementService.h"

using SG::Algebra::Graph;
using SG::Algebra::Matrix;
using SG::DataStructure::Common::Id;
using SG::DBManager::DBServiceFactorySP;
using namespace SG::FEMSolver;
using namespace SG::DBManager;

using IdxSet = std::vector<idx_t>;

MinimumDegreeSort::MinimumDegreeSort ()
{}

void MinimumDegreeSort::SortNodeId (std::vector<SG::DataStructure::Common::Id>& nodeIds, std::vector<std::size_t>& indexes)
{
    //定义一个标志位，用于判定元素之间是否进行了交换
    bool flag{false};
    auto size = nodeIds.size();
    std::size_t temp;
    for (std::size_t i = 0; i < size - 1; i++) 
    {
        // reset `flag`, assumed the vertor is already ordered in this turn.
        flag = false;
        for (std::size_t j = 0; j < size - 1 - i; j++) 
        {
            if (nodeIds[j] > nodeIds[j + 1]) 
            {
                //nodeIds 并非升序，需要交换编号和对应索引， 并将 flag置为true,需要进一步判断
                flag = true;
                temp = nodeIds[j];
                nodeIds[j] = nodeIds[j + 1];
                nodeIds[j + 1] = temp;

                temp = indexes[j];
                indexes[j] = indexes[j + 1];
                indexes[j + 1] = temp;
            }
        }

        //如果没有发生交换，说明数组已经是有序的了，则直接结束排序
        if (!flag) 
        {
            break;
        } 
    }
}

Graph MinimumDegreeSort::GenerateGraph 
(
    const SG::DBManager::DBServiceFactorySP dbServiceFactory, 
    const std::vector<SG::DataStructure::Common::Id>& nodeIds,
    const std::vector<std::size_t>& indexes
)
{
    const auto& eleSumInfoService = dbServiceFactory->get<IElementService>();
    
    // 第一次遍历拓扑关系，统计每个顶点对应的边数量。
    std::size_t nodeSize = nodeIds.size ();
    std::vector<std::size_t> nEdge(nodeSize, 0);
    auto eleTypes = eleSumInfoService -> GetAllElementTypes();
    std::size_t posi;
    for (const auto& eleType: eleTypes)
    {
        //跳过质量单元
        // if (/* condition */)
        // {
        //     /* code */
        // }
        Matrix eleNodes = eleSumInfoService -> GetElementNodes(eleType); // 需要建立类型和数据表的关联。
        auto nEleNode =  eleNodes.GetColSize();
        // 单元没有节点或者仅有一个节点
        if (nEleNode < 2)  continue;
        // 对单元进行循环
        std::size_t eleSize = eleNodes.GetRowSize();
        for (std::size_t iEle = 0; iEle < eleSize; ++iEle)
        {
            // 同一个单元的两个节点形成一条边
            // 通过节点编号 在NodeMap中使用find方法，此处可以使用二分查找，但是还是不够高效， 考虑替换成二叉树
            for (std::size_t iNode = 0; iNode < nEleNode - 1; ++iNode)
            {
                //iIndex： 单元 i节点对应的索引
                auto it =  std::find (nodeIds.begin(), nodeIds.end(), eleNodes(iEle, iNode));
                posi = std::distance(nodeIds.begin(), it);
                auto iIndex = indexes[posi];
                for (std::size_t jNode = iNode + 1; jNode < nEleNode; ++jNode)
                {
                    // jIndex, 单元j节点对应的索引位置
                    it = std::find (nodeIds.begin(), nodeIds.end(), eleNodes(iEle, jNode));
                    posi = std::distance(nodeIds.begin(), it);
                    auto jIndex = indexes[posi];
                    // Fix： metis进行稀疏矩阵排序，需要将两条边都进行排序
                    ++(nEdge[iIndex]);
                    ++(nEdge[jIndex]);
                }
            }
        }

    }
    if (1)
    {
        std::size_t nodeIndex = 0;
        for (auto vSize : nEdge)
        {
            if (vSize < 2)
            {
                std::cout << "independented node " << nodeIds[nodeIndex] << std::endl;
            }
            ++nodeIndex;
        }

    }
    // 生成图的结构
    Graph g(nEdge);
    
    // 再次遍历单元，完成对各个节点邻居的记录
    // pIndex, 用于填入边位置进行计数
    std::vector<std::size_t> pIndex = g.m_pointer;
    for (const auto& eleType: eleTypes)
    {
        // if (/* condition */)
        // {
        //     /* code */
        // }

        Matrix eleNodes = eleSumInfoService -> GetElementNodes(eleType); // 需要建立类型和数据表的关联。
        auto nEleNode =  eleNodes.GetColSize();
        // 单元没有节点或者仅有一个节点
        if (nEleNode < 2)  continue;
        // 对单元进行循环
        std::size_t eleSize = eleNodes.GetRowSize();
        for (std::size_t iEle = 0; iEle < eleSize; ++iEle)
        {
            for (std::size_t iNode = 0; iNode < nEleNode - 1; ++iNode)
            {
                auto it =  std::find (nodeIds.begin(), nodeIds.end(), eleNodes(iEle, iNode));
                posi = std::distance(nodeIds.begin(), it);
                auto iIndex = indexes[posi];
                for (std::size_t jNode = iNode + 1; jNode < nEleNode; ++jNode)
                {
                    it = std::find (nodeIds.begin(), nodeIds.end(), eleNodes(iEle, jNode));
                    posi = std::distance(nodeIds.begin(), it);
                    auto jIndex = indexes[posi];

                    // 记录 i-j边，
                    posi = pIndex[iIndex];
                    // 储存邻居编号
                    g.m_neighbour[posi] = jIndex;
                    // 更新位置， 用于存储i节点的下一个邻居边
                    ++pIndex[iIndex];

                    // 记录 j-i边
                    posi = pIndex[jIndex];
                    g.m_neighbour[posi] = iIndex;
                    ++pIndex[jIndex];
                } // end jNode
            } // end iNode
        }
    }

    // 消除重复边记录。 一条图边可能被两个及以上单元共用。存在重复记录
    int mpt = g.m_pointer[0];
    for(std::size_t vI = 0 ; vI < g.m_pointer.size()-1 ; ++vI)
    {
        // 将顶点 vI 的邻居copy 到 nerghborI
        std::vector<int> nerghborI;
        nerghborI.assign (g.m_neighbour.begin() + mpt, g.m_neighbour.begin() + g.m_pointer[vI+1]);
        // 删除重复出现的邻居
        std::sort(nerghborI.begin(),nerghborI.end());
        nerghborI.erase(unique(nerghborI.begin(),nerghborI.end()),nerghborI.end());
        auto len = nerghborI.size();

        // 将邻居顶点放在正确的位置
        const auto& posi = g.m_pointer[vI];
        for (std::size_t i = 0 ; i < len ;++i)
        {
            g.m_neighbour[i + posi] = nerghborI[i];
        }

        mpt = g.m_pointer[vI+1]; // 记录下一个顶点邻居的起始位置
        // 更新 vI 邻居的结束位置
        g.m_pointer[vI+1] =  g.m_pointer[vI] + len;
    }

    // 删除 neighbour中无效数据
    g.m_neighbour.resize(*(g.m_pointer.end()-1));
    return g;
}

/** @brief 计算节点最小度排序
 * 1. 调用 SortNodeId
 * 2. 调用 GenerateGraph
 * 3. 新的排序映射，获得nodeId 对应组装使用的新id间的映射关系
 * @author Li Jiayang
*/
void MinimumDegreeSort::Compute 
(
    const SG::DBManager::DBServiceFactorySP dbServiceFactory, 
    std::vector<SG::DataStructure::Common::Id>& nodeIds,
    std::vector<std::size_t>& indexes   
)
{
    // 假设节点编号不连续 通过实际节点到重新节点编号的映射
    MinimumDegreeSort::SortNodeId (nodeIds, indexes);
    // 将生成的图传入metis接口， 得到新的排序
    auto g = MinimumDegreeSort::GenerateGraph (dbServiceFactory, nodeIds, indexes);

    // 图数据转换成 metis接口需要的数据格式
    idx_t nvtxs = g.GetNodeSize();
    IdxSet xadj(nvtxs + 1);
    IdxSet adjncy(g.m_neighbour.size());
    for(std::size_t i = 0; i < nodeIds.size() + 1; ++i)
    {
        xadj[i]= g.m_pointer[i];
    }
    for(std::size_t i = 0; i < g.m_neighbour.size(); ++i)
    {
       adjncy[i]= g.m_neighbour[i];
    }

    // 为输出数据开辟空间
    IdxSet perm(nvtxs);
    IdxSet iperm(nvtxs);

    idx_t options[METIS_NOPTIONS];
    METIS_SetDefaultOptions (options);
    options[METIS_OPTION_NUMBERING] = 0;
    int status = METIS_NodeND(&nvtxs,xadj.data(),adjncy.data(), NULL, options, _OUT perm.data(),  _OUT iperm.data());

    // nodeNew
    for(std::size_t i = 0; i < nodeIds.size(); ++i)
    {
        printf("%d \n",perm[i]);
    }
    std::cout << "===========================\n";
    for(std::size_t i = 0; i < nodeIds.size(); ++i)
    {
        printf("%d \n",iperm[i]);
    }
}
